import java.util.Arrays;

/**
 * 桶排序
 * 算是计数排序的升级版
 * 计数排序：若数组元素范围为 [0, 10000]，那么计数排序需要创建 10001 个桶
 * 桶排序：若数组元素范围为 [0, 10000]，那么基数排序的桶数量，由自定义的桶容量决定
 *  若设置桶容量为 10，则需要 (10000 - 0) / 10 + 1 = 1001 个桶
 *  若设置桶容量为 50，则需要 (10000 - 0) / 50 + 1 = 201 个桶
 *  桶容量越大，桶个数越小
 *
 * 1.桶的容量：视排序数组中的元素范围而定
 * 2.桶的个数：根据排序数组中的最大最小值计算出
 *      (最大值 - 最小值) / 桶容量 + 1
 * 3.将排序数组中的元素，分配到桶中
 * 4.对每个桶都进行排序（桶中的元素不会太多）
 * 5.桶中排好序的元素，放入到 res 中
 *
 * bucket[1] 桶中的元素一定大于等于 bucket[0] 中的元素
 */
public class BucketSort {
    public static int[] bucketSort(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        // 桶的容量：10 个元素
        int bucketSize = 10;
        int minVal = nums[0];
        int maxVal = nums[0];
        for (int num : res) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }
        // 桶的个数
        int bucketCnt = (maxVal - minVal) / bucketSize + 1;
        int[][] bucket = new int[bucketCnt][0];
        for (int num : res) {
            // 遍历数组，将元素分配到桶中
            int idx = (num - minVal) / bucketSize;
            bucket[idx] = enlargeSize(bucket[idx], num);
        }
        int i = 0;
        // 对每个桶，进行（插入）排序，排序后的元素，放入 res 中
        for (int[] arr : bucket) {
            int[] temp = InsertSort.insertSort(arr);
            for (int num : temp) {
                res[i ++] = num;
            }
        }
        return res;
    }

    /**
     * 将数组扩容一个单位，并将元素 i 加入到数组末尾
     */
    public static int[] enlargeSize(int[] bucket, int i) {
        bucket = Arrays.copyOf(bucket, bucket.length + 1);
        bucket[bucket.length - 1] = i;
        return bucket;
    }
}
